@datastructures-js/binary-search-tree

@datastructures-js/binary-search-tree

Binary Search Tree & AVL Tree (Self Balancing Tree) implementation in javascript.

Binary Search Tree
AVL Tree (Self Balancing Tree)

Table of Contents

• Install
• API
  • require
  • import
  • Construction
  • .insert(key, value)
  • .has(key)
  • .find(key)
  • .min()
  • .max()
  • .root()
  • .count()
  • .traverseInOrder(cb)
  • .traversePreOrder(cb)
  • .traversePostOrder(cb)
  • .remove(key)
  • .clear()
  • BinarySearchTreeNode
  • AvlTreeNode
• Build
• License

install

npm install --save @datastructures-js/binary-search-tree

API

Both trees have the same interface except that AVL tree will maintain itself balanced by rotating the nodes that become unbalanced during insertion and deletion. If your code requires a strictly balanced tree that always benefits from the log(n) runtime of insert & remove, you should use the AVL one.

require

const { BinarySearchTree, AvlTree } = require('@datastructures-js/binary-search-tree');

import

import { BinarySearchTree, AvlTree } from '@datastructures-js/binary-search-tree';

Construction

const bst = new BinarySearchTree();

// OR a self balancing tree

const bst = new AvlTree();

.insert(key, value)

inserts a node with key/value into the tree. Inserting an node with existing key, would update the existing node's value with the new one. AVL tree will rotate nodes properly if the tree becomes unbalanced during insertion.

params
name	type
key	number or string
value	object

return
BinarySearchTree	BinarySearchTreeNode
AvlTree	AvlTreeNode

runtime
O(log(n))

Example

bst.insert(50, 'v1');
bst.insert(80, 'v2');
bst.insert(30, 'v3');
bst.insert(90, 'v4');
bst.insert(60, 'v5');
bst.insert(40, 'v6');
bst.insert(20, 'v7');

.has(key)

checks if a node exists by its key.

params
name	type
key	number or string

return
boolean

runtime
O(log(n))

Example

bst.has(50); // true
bst.has(100); // false

.find(key)

finds a node in the tree by its key.

params
name	type
key	number or string

return
BinarySearchTree	BinarySearchTreeNode
AvlTree	AvlTreeNode

runtime
O(log(n))

Example

const n60 = bst.find(60);
console.log(n60.getKey()); // 60
console.log(n60.getValue()); // v5

console.log(bst.find(100)); // null

.min()

finds the node with min key in the tree.

return
BinarySearchTree	BinarySearchTreeNode
AvlTree	AvlTreeNode

runtime
O(log(n))

Example

const min = bst.min();
console.log(min.getKey()); // 20
console.log(min.getValue()); // v7

.max()

finds the node with max key in the tree.

return
BinarySearchTree	BinarySearchTreeNode
AvlTree	AvlTreeNode

runtime
O(log(n))

Example

const max = bst.max();
console.log(max.getKey()); // 90
console.log(max.getValue()); // v4

.root()

returns the root node of the tree.

return
BinarySearchTree	BinarySearchTreeNode
AvlTree	AvlTreeNode

runtime
O(1)

Example

const root = bst.root();
console.log(root.getKey()); // 50
console.log(root.getValue()); // v1

.count()

returns the count of nodes in the tree.

return
number

runtime
O(1)

Example

console.log(bst.count()); // 7

.traverseInOrder(cb)

traverses the tree in order (left-node-right).

params
name	type	description
cb	function	called with each node

runtime
O(n)

Example

bst.traverseInOrder((node) => console.log(node.getKey()));

/*
20
30
40
50
60
80
90
*/

.traversePreOrder(cb)

traverses the tree pre order (node-left-right).

params
name	type	description
cb	function	called with each node

runtime
O(n)

Example

bst.traversePreOrder((node) => console.log(node.getKey()));

/*
50
30
20
40
80
60
90
*/

.traversePostOrder(cb)

traverses the tree post order (left-right-node).

params
name	type	description
cb	function	called with each node

runtime
O(n)

Example

bst.traversePostOrder((node) => console.log(node.getKey()));

/*
20
40
30
60
90
80
50
*/

.remove(key)

removes a node from the tree by its key. AVL tree will rotate nodes properly if the tree becomes unbalanced during deletion.

params
name	type
key	number or string

return
boolean

runtime
O(log(n))

Example

bst.remove(20); // true
bst.remove(100); // false
console.log(bst.count()); // 6

.clear()

clears the tree.

runtime
O(1)

Example

bst.clear();
console.log(bst.count()); // 0
console.log(bst.root()); // null

BinarySearchTreeNode

.getKey()

returns the node's key that is used to compare with other nodes.

return
number or string

.setValue(value)

change the value that is associated with a node.

params
name	type
value	object

.getValue()

returns the value that is associated with a node.

return
object

.getLeft()

returns node's left child node.

return
BinarySearchTree	BinarySearchTreeNode
AvlTree	AvlTreeNode

.getRight()

returns node's right child node.

return
BinarySearchTree	BinarySearchTreeNode
AvlTree	AvlTreeNode

.getParent()

returns node's parent node.

return
BinarySearchTree	BinarySearchTreeNode
AvlTree	AvlTreeNode

AvlTreeNode

extends BinarySearchTreeNode and adds the following methods:

.getHeight()

the height of the node in the tree. root height is 1.

return
number

.getLeftHeight()

the height of the left child. 0 if no left child.

return
number

.getRightHeight()

the height of the right child. 0 if no right child.

return
number

.calculateBalance()

returns the node's balance by subtracting right height from left height.

return
number

Build

grunt build

License

The MIT License. Full License is here